Robust Outlier Detection Using Commute Time and Eigenspace Embedding.

A Robust Decision Tree Algorithm for Imbalanced Data Sets.

Angle Tree Nearest Neighbor Search in High Dimensions with Low Intrinsic Dimensionality

Outlier detection special issue.


Mining adversarial patterns via regularized loss minimization.


New Frontiers in Applied Data Mining

Robust record linkage blocking using suffix arrays.

A Game Theoretical Model for Adversarial Learning.
Many data mining applications, ranging from spam filtering to intrusion detection, are faced with active adversaries. In all these applications, initially successful classifiers will degrade easily. This becomes a game between the adversary and the data miner: The adversary modifies its strategy to avoid being detected by the current classifier; the data miner then updates its classifier based on the new threats. In this paper, we investigate the possibility of an equilibrium in this seemingly never ending game, where neither party has an incentive to change. Modifying the classifier causes too many false positives with too little increase in true positives; changes by the adversary decrease the utility of the false negative items that aren’t detected. We develop a game theoretic framework where the equilibrium behavior of adversarial learning applications can be analyzed, and provide a solution for finding the equilibrium point. A classifier’s equilibrium performance indicates its eventual success or failure. The data miner could then select attributes based on their equilibrium performance, and construct an effective classifier. 1
Association Rules Network Definition and Applications.
Abstract: The role of data mining is to search “the space of candidate hypotheses ” to offer solutions, whereas the role of statistics is to validate the hypotheses offered by the data-mining process. In this paper we propose Association Rules Networks (ARNs) as a structure for synthesizing, pruning, and analyzing a collection of association rules to construct candidate hypotheses. From a knowledge discovery perspective, ARNs allow for a goal-centric, context-driven analysis of the output of association rules algorithms. From a mathematical perspective, ARNs are instances of backward-directed hypergraphs. Using two extensive case studies, we show how ARNs and statistical theory can be combined to generate and test hypotheses. © 2009 Wiley Periodicals,
Disk%2DBased Sampling for Outlier Detection in High Dimensional Data.

Spatio%2Dtemporal Outlier Detection in Precipitation Data.

Patterns%2C Complex.
In this study, three measures of temporal pattern complexity were compared as regards their perceptual validity. The first measure, based on the work of Tanguiane (1993), uses the idea that a temporal pattern can be described in terms of (elaborations of) more simple patterns, simultaneously at different levels. The second measure is based on the complexity measure for finite sequences proposed by Lempel and Ziv (1976), which is related to the number of steps in a self-delimiting production process by which such a sequence is presumed to be generated. The third measure, newly developed here, is rooted in the theoretical framework of rhythm perception of Povel and Essens (1985). It takes into account the ease of coding a temporal pattern and the complexity of the segments resulting from this coding. The perceptual validity of the three measures was evaluated in an experiment in which subjects judged the complexity of 35 temporal patterns. Correlations between the three measures and the ...
Mining spatio%2Dtemporal patterns in object mobility databases.

Using Significant
In an earlier paper, we introduced a new “boosting” algorithm called AdaBoost which, theoretically, can be used to significantly reduce the error of any learning algorithm that consistently generates classifiers whose performance is a little better than random guessing. We also introduced the related notion of a “pseudo-loss ” which is a method for forcing a learning algorithm of multi-label conceptsto concentrate on the labels that are hardest to discriminate. In this paper, we describe experiments we carried out to assess how well AdaBoost with and without pseudo-loss, performs on real learning problems. We performed two sets of experiments. The first set compared boosting to Breiman’s “bagging ” method when used to aggregate various classifiers (including decision trees and single attribute-value tests). We compared the performance of the two methods on a collection of machine-learning benchmarks. In the second set of experiments, we studied in more detail the performance of boosting using a nearest-neighbor classifier on an OCR problem. 
Spatio%2DTemporal Analysis of the Relationship between South American Precipitation Extremes and the El Ni%F1o Southern Oscillation.

An incremental data%2Dstream sketch using sparse random projections.
incremental data-stream sketch using sparse random projections ∗
High Confidence Rule Mining for Microarray Analysis.

Mining Spatio%2Dtemporal Association Rules
Abstract. As mobile devices proliferate and networks become more locationaware, the corresponding growth in spatio-temporal data will demand analysis techniques to mine patterns that take into account the semantics of such data. Association Rule Mining has been one of the more extensively studied data mining techniques, but it considers discrete transactional data (supermarket or sequential). Most attempts to apply this technique to spatial-temporal domains maps the data to transactions, thus losing the spatio-temporal characteristics. We provide a comprehensive definition of spatio-temporal association rules (STARs) that describe how objects move between regions over time. We define support in the spatio-temporal domain to effectively deal with the semantics of such data. We also introduce other patterns that are useful for mobility data; stationary regions and high traffic regions. The latter consists of sources, sinks and thoroughfares. These patterns describe important temporal characteristics of regions and we show that they can be considered as special STARs. We provide efficient algorithms to find these patterns by exploiting several pruning properties 1. 1
Geometrically Inspired Itemset Mining.
In our geometric view, an itemset is a vector (itemvector) in the space of transactions. The support of an itemset is the generalized dot product of the participating items. Linear and potentially nonlinear transformations can be applied to the itemvectors before mining patterns. Aggregation functions can be applied to the transformed vectors and pushed inside the mining process. We show that interesting itemset mining can be carried out by instantiating four abstract functions: a transformation (g), an algebraic aggregation operator (◦) and measures (f and F). For frequent itemset mining (FIM), g and F are identity transformations,  ◦ is intersection and f is the cardinality. Based on the geometric view we present a novel algorithm that uses space linear in the number of 1-itemsets to mine all interesting itemsets in a single pass over this data, with no candidate generation. It scales (roughly) linearly in running time with the number of interesting itemsets. FIM experiments show that it outperforms FP-Growth on realistic datasets above a small support threshold (0.29 % and 1.2 % in our experiments). 1
CCCS a top%2Ddown associative classifier for imbalanced class distribution.

Mining for Outliers in Sequential Databases.

Mining for Outliers in Sequential Databases.

SLOM a new measure for local spatial outliers.

A Hill%2DClimbing Landmarker Generation Algorithm Based on Efficiency and Correlativity Criteria.
For a given classification task, there are typically several learning algorithms available. The question then arises: which is the most appropriate algorithm to apply. We recently proposed a new algorithm for making such a selection based on landmarking- a recent meta-learning strategy that utilises meta-features that are themselves efficient learning algorithms. This algorithm, which creates a set of landmarkers that each utilise subsets of the algorithms being landmarked, was shown to be able to estimate accuracy well, even when employing a small fraction of the given algorithms. However, that version of the algorithm had an exponential training time computational complexity. In this paper, we propose a hill-climbing version of the landmarker generation algorithm, which requires only polynomial training time complexity. Our experiments show that the landmarkers formed, have similar results to the more complex version of the algorithm. 1.
Conditional Random Fields for Transmembrane Helix Prediction.
Abstract. It is estimated that 20 % of genes in the human genome code for integral membrane proteins(IMPs) and some estimates are much higher. IMPs control a broad range of events essential to the proper functioning of cells, tissues and organisms. IMPs include the most common targets of clinically useful drugs, such as the G protein coupled receptors (GPCR), the target for more than 50 % of prescription drugs [1]. However there is a dearth of high-resolution 3D structural information on the IMPs. The number of the IMPs depositions in the major structural holding, the Protein Data Bank is less than 0.4 % of the collection [2]. Therefore good prediction methods of IMPs structures are to be highly valued. In this paper we apply Conditional Random Fields (CRFs) to build a probabilistic model to segment and label sequence data to solve the membrane protein helix prediction problem. The advantage of a CRFs is that it allows seamless integration of biological domain knowledge into the model. Our results show that the CRF model outperforms other well known helix prediction approaches on several important measures. 1
Striking Two Birds With One Stone Simultaneous Mining of Positive and Negative Spatial Patterns.

A Landmarker Selection Algorithm Based on Correlation and Efficiency Criteria.
Abstract. Landmarking is a recent and promising meta-learning strategy, which defines meta-features that are themselves efficient learning algorithms. However, the choice of landmarkers is often made in an ad hoc manner. In this paper, we propose a new perspective and set of criteria for landmarkers. Based on the new criteria, we propose a landmarker generation algorithm, which generates a set of landmarkers that are each subsets of the algorithms being landmarked. Our experiments show that the landmarkers formed, when used with linear regression are able to estimate the accuracy of a set of candidate algorithms well, while only utilising a small fraction of the computational cost required to evaluate those candidate algorithms via ten-fold cross-validation. 1
Mining Complex Relationships in the SDSS SkyServer Spatial Database.

Comparisons between Heuristics Based on Correlativity and Efficiency for Landmarker Generation.
In this paper we propose a new meta-learning approach using landmarking. This approach, which is based on a new set of criteria for selecting landmarkers, generates a set of landmarkers that are each subsets of the candidate algorithms being landmarked. In our experiments, we compare three heuristics based on correlativity and the efficiency gained. With each heuristic, the landmarkers generated using linear regression were able to estimate accuracy well, even when only utilizing a small fraction of the given algorithms. The results also show that the heuristic in which efficiencies are estimated via 1-nearest neighbor outperformed the other heuristics. 1
On Local Pruning of Association Rules Using Directed Hypergraphs.
In this paper we propose an adaptive local pruning method for association rules. Our method exploits the exact mapping between a certain class of association rules, namely those whose consequents are singletons and backward directed hypergraphs. The hypergraph which represents the association rules is called an Association Rules Network(ARN). We propose two operations on this network for pruning rules, prove several properties of the ARN and apply the results of our approach to two popular data sets. Keywords: Association Rules Pruning, Interestingess, Directed Hypergraphs  1 
On Local Spatial Outliers.
We propose a measure, Spatial Local Outlier Measure (SLOM) which captures the local behaviour of datum in their spatial neighborhood. With the help of SLOM we are able to discern local spatial outliers which are usually missed by global techniques like “three standard deviations away from the mean”. Furthermore the measure takes into account the local stability around a data point and supresses the reporting of outliers in highly unstable areas, where data is too heterogeneous and the notion of outliers is not meaningful. We prove several properties of SLOM and report experiments on synthetic and real data sets which show that our approach is novel and scalable to large data sets. 1 Introduction and Related Work
A new landmarker generation algorithm based on correlativity.
Landmarking is a recent and promising metalearning strategy, which defines meta-features that are themselves efficient learning algorithms. However, the choice of landmarkers is made in an ad hoc manner. In this paper, we propose a new perspective and set of criteria for landmarkers. With these, we introduce a landmarker generation algorithm, which creates a set of landmarkers that each utilise subsets of the algorithms being landmarked. The experiments show that the landmarkers formed, when used with linear regression, are able to estimate accuracy well, even when utilising a small fraction of the given algorithms. 1.
Mining Open Source Software %28OSS%29 Data Using Association Rules Network.
The Open Source Software(OSS) movement has attracted considerable  attention in the last few years. In this paper we report our results of mining   data acquired from SourceForge.net, the largest open source software hosting  website. In the process we introduce Association Rules Network(ARN), a  (hyper)graphical model to represent a special class of association rules. Using  ARNs we discover important relationships between the attributes of successful  OSS projects. We verify and validate these relationships using Factor Analysis, a  classical statistical technique related to Singular Value Decomposition(SVD).
Complex Spatial Relationships.
This paper describes the need for mining complex relationships in spatial data. Complex relationships are defined as those involving two or more of: multi-feature colocation, self-colocation, one-to-many relationships, self-exclusion and multi-feature exclusion. We demonstrate that even in the mining of simple relationships, knowledge of complex relationships is necessary to accurately calculate the significance of results. We implement a representation of spatial data such that it contains known `weak-monotonic&#039; properties, which are exploited for the efficient mining of complex relationships, and discuss the strengths and limitations of this representation.
Mining Open Source Software %28OSS%29 Data Using Association Rules Network.
The Open Source Software(OSS) movement has attracted considerable  attention in the last few years. In this paper we report our results of mining   data acquired from SourceForge.net, the largest open source software hosting  website. In the process we introduce Association Rules Network(ARN), a  (hyper)graphical model to represent a special class of association rules. Using  ARNs we discover important relationships between the attributes of successful  OSS projects. We verify and validate these relationships using Factor Analysis, a  classical statistical technique related to Singular Value Decomposition(SVD).
A Comparison of Markov Random Field and Spatial Regression Models for Mining Geospatial Data.

Efficient Join%2DIndex%2DBased Spatial%2DJoin Processing A Clustering Approach.

Spatial contextual classification and prediction models for mining geospatial data.
Modeling spatial context (e.g., autocorrelation) is a key challenge in classification problems that arise in geospatial domains. Markov Random Fields (MRFs) is a popular model for in-corporating spatial context into image segmentation and land-use classification problems. The spatial autoregression model (SAR) which is an extension of the classical regression model for incorporating spatial dependence, is popular for prediction and classification of spatial data in regional economics, natural resources, and ecological studies. There is little literature comparing these alternative approaches to facilitate the exchange of ideas (e.g., solution procedures). We argue that the SAR model makes more restrictive assumptions about the distribution of feature values and class boundaries than MRF. The relationship between SAR and MRF is analogous to the relationship between regression and Bayesian classifiers. This paper provides comparisons between the two models using a probabilistic and an experimental framework.
Maintaining Spatial Constraints Using a Dimension Graph Approach.

Extending Data Mining for Spatial Applications A Case Study in Predicting Nest Locations.
Spatial data mining is a process to discover interesting and potentially useful spatial patterns embedded in spatial databases. Efficient tools for extracting information from spatial data sets can be of importance to organizations which own, generate and manage large geo-spatial data sets. The current approach towards solving spatial data mining problems is to use classical data mining tools after &#034;materializing&#034; spatial relationships and assuming independence between different data points. However, classical data mining methods often perform poorly on spatial data sets which have high spatial auto-correlation. In this paper we will review spatial statistical techniques which can effectively model the notion of spatial-autocorrelation and apply it to the problem of predicting bird nest locations in a wetland.  Keywords: Spatial data mining, spatial autocorrelation, spatial autoregression.  1 Introduction  Widespread use of spatial databases [9, 19] is leading to an increasing interest...
Processing object%2Doientation%2Dbased direction queries a summary of results.

Consistency checking for Euclidean spatial constraints a dimension graph approach.
In this paper, we address the problem of consistency checking for Euclidean spatial constraints. A dimension graph representation is pmposed to maintain the Euclidean spatial constraints among objects. The basic idea is to project the spatial constraints on both X and Y dimensions, and to construct a dimension graph on each dimension. Using a dimension graph representation transfonns the problem of consistency checking into the problem of graph cycle detection. Consistency checking can be achieved with O(N+E) time as well as space complexity, where N is the number of spatial objects, and E is the number of spatial predicates in the constraint. The proposed approach is faster than O(N2) when the number of predicates is much smaller than N2 and there are few disjunctions in the spatial constraint. The dimension graph and consistency checking algorithm can be used for points, intervals and polygons in two-dimensional space. The algorithm can also guarantee global consistency.
Predicting Locations Using Map Similarity%28PLUMS%29 A Framework for Spatial Data Mining.
Spatial data mining is a process to discover interesting, potentially useful and high utility  patterns embedded in spatial databases. Efficient tools for extracting information from spatial  data sets can be of importance to organizations which own, generate and manage large spatial  data sets. The current approach towards solving spatial data mining problems is to use classical  data mining tools after &#034;materializing&#034; spatial relationships. However, the key property of  spatial data is that of spatial autocorrelation. Like temporal data, spatial data values are  influenced by values in their immediate vicinity. Ignoring spatial autocorrelation in the modeling  process leads to results which are a poor-fit and unreliable. In this paper we will propose  PLUMS(Predicting Locations Using Map Similarity), a new approach for supervised spatial  data mining problems. PLUMS searches the space of solutions using a map-similarity measure  which is more appropriate in the context of spatial dat...
Spatial Pictogram Enhanced Conceptual Data Models and Their Translation to Logical Data Models.
Abstract. The successful development ofany geographic information system project needs the careful design and implementation of spatial databases via conceptual and logical data-modeling. This involves understanding the underlying spatial data model, spatial data types and operators, spatial query languages and spatial indexing techniques. Conventional entity-relationship diagrams have limitations for conceptual spatial data-modeling, since they get cluttered with numerous spatial relationships. In addition the logical data model gets cluttered with redundant tables representing materialization of the M:N spatial relationships. In this paper we present an extension to ER diagrams using pictograms for entities and as well as relationships. This approach e ectively reduces the cluttering, as spatial relationships will become implicit. We have provided a complete grammar using \yacc &amp;quot; like syntax to translate the pictogram-extended ER diagram into a SQL3-level logical data model using OGIS-standard spatial data types.
An Object Model of Direction and Its Implications.
Direction is an important spatial concept that is used in many fields such as geographic information systems(GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. Previous work has modeled direction as a relational predicate between spatial objects. Conversely, in this paper, we model direction as a new kind of spatial object using the concepts of vectors, points and angles. The basic approach is to model direction as a unit vector. This novel view of direction has several obvious advantages: Being modeled as a spatial object, a direction object can have its own attributes and operation set. Secondly, new spatial data types such as oriented spatial objects and open spatial objects can be defined at the abstract object level. Finally, the object view of direction makes direction reasoning easy and also reduces the need for a large number of inference rules. These features are important in spatial query processing and optimization. The app...
Spatial Databases %2D Accomplishments and Research Needs.
Spatial databases have been an active area of research for over two decades, addressing the growing data management and analysis needs of spatial applications such as Geographic Information Systems. This research has produced a taxonomy of models for space, spatial data types and operators, spatial query languages and processing strategies, as well as spatial indexes and clustering techniques. However, more research is needed to improve support for network and eld data, as well as query processing (e.g. cost models, bulk load). Another important need is to apply the spatial data management accomplishments to newer applications such as data warehouses and multimedia information systems. The objective of this paper is to identify recent accomplishments and the research needs in the near term.
Optimizing Join Index Based Join Processing A Graph Partitioning Approach.

